package algorithm;

import static algorithm.eightQueen.nQueen.check;
import static algorithm.eightQueen.nQueen.checkerBoard;
import static algorithm.eightQueen.nQueen.count;
import static algorithm.eightQueen.nQueen.init;
import static algorithm.eightQueen.nQueen.num;

import algorithm.eightQueen.Queen;

public class Backtracking {


  // backtracking
  public static boolean putIn(Queen queen) {
    if (queen.x >= num) {
      count++;
//      print();
      return true;
    }
    if (queen.y >= num) {
      return false;
    }
    boolean flag = false;
    for (int i = queen.y; i < num; i++) {
      queen.y = i;
      if (check(queen)) {
        checkerBoard.get(queen.x).set(queen.y, queen);
        flag = putIn(new Queen(queen.x + 1, 0, queen.val + 1));
        if (!flag) { //去掉这个判断可以获取所有解
          checkerBoard.get(queen.x).set(queen.y, new Queen());
        }
      }
    }
    return flag;
  }


  public static void main(String[] args) {
    init();
    long start = System.currentTimeMillis();
    putIn(new Queen(0, 0, 1));
    System.out.println(System.currentTimeMillis() - start);
  }

}
